Parsing: Context-Free Grammars
Table of Contents
| Phase | Input | Output |
|---|---|---|
| Lexer | String of chars | String of tokens |
| Parser | String of tokens | Parse Tree |
1. Context-Free Grammars (CFGs)
parsers must distinguish between valid and invalid strings of tokens. So we need a language for describing valid string of tokens, and a method for distinguish valid from invalid strings of tokens.
PL has recursive structures, e.g., while loop inside an if statement. CFGs are a natural notation for describing this recursive structures.
A CFG consists of
- a set of terminals \(T\). Called terminal since no rules can be used to replace them.
- a set of symbol \(N\)
- a start symbol \(S\), which should be a non-terminal
- a set of productions (generation rules):
- We can begin with a string with only the start symbol \(S\)
- Replace any non-terminal \(X\) in the string with productions
- Repeat step 2 until there are no non-terminals in the string
Let \(G\) be a context-free grammar with start symbol \(S\), then the language of \(G\) is
\[ \set{ a_1\dots a_n : S\to a_1\dots a_n \text{ and every \(a_i\) is a terminal} } \]
1.1. Derivation
- Derivation
- A derivation is a sequence of productions.
- Parse tree
- Derivation can be drawn as a tree: for a production \( X \to Y_1\dots Y_n \), we append \(Y_i\) as children of \(X\). This tree is called parse tree. Terminals are the leaves and non-terminals are interior nodes. The parse tree shows the association of operations while the input string does not.
Left-most and right-most derivations are equivalent.
1.2. Ambiguity
- Ambiguity
- A grammar is ambiguous if it has more than one parse tree for some string.
Solution: precedence and associativity declaration.